package recursion;

import java.util.Arrays;

public class QuicklySort {
    public static void main(String[] args) {
        //定义数组--------------------[57, 31, 85, 71, 71, 64, 54, 80, 92, 77]
        //[62, 79, 46, 13, 43, 26, 32, 73, 2, 53][3, 1, 90, 21, 37, 65, 25, 25, 83, 23]
        int[] arr = new int[10];
        for (int i=0;i<arr.length;i++) {
            arr[i] = (int)(Math.random()*100)+1;
        }
//        int[] arr = new int[]{3, 1, 90, 21, 37, 65, 25, 25, 83, 23};
        System.out.println(Arrays.toString(arr));

        //快速排序-------------------------
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

//    public static void quickSort(int[] arr,int left,int right) {
        //双层循环
//        if (left >= right) {
//            return;
//        }
//
//        int temp = arr[left];
//        int j = right;
//        int i = left;
//
//        for (;j > i; j--) {
//            if (arr[j] < temp) {
//                arr[i] = arr[j];
//                for (; i < j && arr[i] < temp; i++) { }
//                arr[j] = arr[i];
//            }
//        }
//        arr[i] = temp;
//        quickSort(arr, left, i - 1);
//        quickSort(arr, i + 1, right);

        //并列循环
//        if (left >= right) {
//            return;
//        }
//        int i = left;
//        int j = right;
//        int temp = arr[i];
//        while (i < j) {
//            while (i<j && arr[j] >= temp) {
//                j--;
//            }
//            arr[i] = arr[j];
//            while (i<j && arr[i] <= temp) {
//                i++;
//            }
//            arr[j] = arr[i];
//        }
//
//        arr[i] = temp;
//        quickSort(arr, left, i - 1);
//        quickSort(arr, i + 1, right);

    //-----------随机取中间值-------------------------------------------------------
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int index = (int)(Math.random()*(right+1-left))+left;   //-----+1  -1  ----  +1覆盖left和right
        int temp = arr[index];
        int i = left;
        int j = right;
        while (j >= index && arr[j] >= temp) {  //-----等于号不能省  循环不会停止  j>i不行
            j--;
        }
        arr[index] = arr[j];
        while (i < j) {
            while (i < j && arr[i] <= temp) {    //----------------arr[index]=arr[i]  不对
                i++;
            }
            arr[j] = arr[i];
            while (j > i && arr[j] >= temp) {
                j--;
            }
            arr[i] = arr[j];
        }
        arr[i] = temp;
        int mid = i;
        quickSort(arr, left, mid-1);
        quickSort(arr, mid + 1, right);
    }

    //-----练习
//    public static void quickSort(int[] arr, int left, int right) {
//        int i = left;
//        int j = right;
//
//        int index = (int) (Math.random() * (right - left)) + left;
//    }
}
